﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PathFinding
{
	class DijkstraPathFindingEngine : IPathFindingEngine
	{
		public DijkstraPathFindingEngine()
		{
		}

		#region IPathFindingEngine Members

		public IIntersection[] GetShortestRoute(IIntersection start, IIntersection destination)
		{
			// Zoek kortste route
			List<IIntersection> toCheck = new List<IIntersection>();
			toCheck.Add(start);

			IIntersection temp = CalcNextIntersection(toCheck);
			while (temp != null && temp != destination)
			{
				temp = CalcNextIntersection(toCheck);
				OnStep();
			}

			IIntersection[] result = null;

			IIntersection currentI = temp;
			List<IIntersection> route = new List<IIntersection>();
			if (temp != null)
			{
				while (currentI != start)
				{
					route.Add(currentI);
					currentI = currentI.PreviousNode;
				}
				route.Add(start);

				result = new IIntersection[route.Count];
				int counter = 0;
				for (int index = route.Count - 1; index >= 0;  index--)
				{
					result[counter] = route[index];
					counter++;
				}
			}

			return result ;
		}

		#endregion

		private IIntersection CalcNextIntersection(List<IIntersection> toCheck)
		{
			IIntersection checkPoint = null;

			var qry = from IIntersection i in toCheck
					  where !i.IsCalculated
					  orderby i.Weight ascending
					  select i;

			foreach (IIntersection i in qry)
			{
				checkPoint = i;
				checkPoint.IsCalculated = true;
				break;
			}

			if (checkPoint != null)
			{
				toCheck.Remove(checkPoint);

				if (checkPoint.Neighbours != null)
				{
					foreach (IIntersection i in checkPoint.Neighbours)
					{
						if (!i.IsCalculated)
						{
							double newWeight = checkPoint.Weight + checkPoint.GetDistance(i);
							if (i.Weight > newWeight || i.PreviousNode == null)
							{
								i.Weight = newWeight;
								i.PreviousNode = checkPoint;
								toCheck.Add(i);
							}
						}
					}
				}
			}

			return checkPoint;
		}

		private void OnStep()
		{
			if (Step != null) Step(this, new EventArgs());
		}
		public event EventHandler Step;
	}
}
